1. Field of the Invention
The present invention relates to a pattern generation method of burst errors existing in a received information, and a detection and correction apparatus for burst errors, or for byte errors which are a special form of burst errors.
2. Description of the Prior Art
In the received information stored in a continuous recording medium, such as magnetic recording or optical recording, not only random errors but also burst errors are frequently occurred. In the information communication systems used under circumstance of susceptible influence by electromagnetic noises or cosmic particles, burst errors are also dominant type of errors. In addition, the possibility that burst errors occur becomes much high in the signal communication in deep cosmos and the communication to/from the satellite.
Information transmission and reception are processed bit by bit in the conventional magnetic disks, optical disks and communication systems. That is, the information is transmitted and received sequentially in these systems. Therefore, error correction and detection should also be performed sequentially. From this viewpoint, sequential processing of error correction and detection can be performed by using linear feedback shift registers (LFSRs) defined by code generator polynomial.
It is well known that Fire code can control burst error correction and detection. This code is defined by the following generator polynomial:g(X)=(Xc+1)p(X)where p(x) is an m-th degree irreducible polynomial on Galois Field GF(2). It is assumed that the period of p(x) is f. Under the condition that f is not divisible by c, where c≧2b−1 and m≧b, burst errors up to length of b can be corrected. At this time, the code length n is shown as n=LCM(f, c) and the check length r becomes r=c+m, where LCM(f, c) represents the smallest common multiple of f and c. This code and its decoder circuit are described in, for example, pp. 212 to 219 of “Coding Theory” written by Hideki Imai and published by Corona Publishing Co. Ltd. in March 1990. This says, however, that the decoder circuit corrects errors sequentially, that is, performs decoding synchronously with clocks by using LFSRs prescribed by p(x) and xc+1.
On the other hand, techniques for detecting and correcting random 1-bit or 2-bit errors in parallel have already been proposed and practically applied. In other words, in high speed semiconductor memory systems, 1-bit, 2-bit random errors, or single cluster of multiple-bit errors, that is, single byte errors are detected or corrected in parallel manner for information bit length of 16 bits to 128 bits read out in parallel from the memory. In this case, decoder circuit should be implemented by combinational circuits, not by LFSRs. These are described in Chapters 4 and 5 of T. R. N. Rao and E. Fujiwara, “Error Control Coding for Computer Systems,” Prentice-Hall, 1989.
It is well known the technique to control the burst errors without directly using the code that has the functionality for the burst error detection and correction. In other words, in case of correcting burst errors having b-bit length included in the information having the n-bit length, the technique of interleaving with degree b can be applied. That is, it is realized by preparing b sets of functions of correcting a 1-bit error for the information having the length of n/b. The technique of interleaving is explained in p. 220 of the “Coding Theory” written by Hideki Imai and published by Corona Publishing Co. Ltd. At this time, if b sets of 1-bit error correction circuits with a parallel decoding capability can be prepared in parallel, the b-bit burst error correcting circuit in parallel manner can be performed. But, in case that the burst error length to be corrected becomes large such as several ten bits, the number of required check bits becomes extremely large, and the quantity of circuit also becomes large. From the practical viewpoint, therefore, this technique cannot be applied.
As a medium on which a three-dimensional image is stored, there is a holographic memory having a super large capacity. For example, in such a memory, not only a two-dimensional image but also a three-dimensional image can be restored by applying laser light to a holographic surface. Information of the light intensity and phase is stored in the holographic memory. The information is read out by applying the laser light to the holographic memory, and the information thus read out is stored temporarily in, for example, a plane-like CCD memory. At this time, the information is read out as each one-dimensional direction data, that is, as longitudinal direction data and as lateral direction data. In this case, the read-out operation is performed at several hundred bits to several ten thousand bits in parallel at a time, and this operation is repeated. By these repeated operations, the information stored on the CCD is read out and the original image is restored. In such a memory, generally, as the recording surface is two-dimensional, the manufacture defects, distortion and cracks in a holographic surface, and interference between the information pieces read out from the holographic memory become two-dimensionally spread plane-like faults. These two-dimensionally spread faults are restored on the CCD as well, as two-dimensional errors. In the case where information is read out from the CCD as each, one-dimensional direction data, the information including burst errors are obtained. This parallel reading action is repeated in succession. Therefore, it is evident that the burst errors included in the information obtained by reading out several hundred bits to several ten thousand bits at a time must be detected and corrected at high speed. In other words, the parallel decoding is essential.
Especially for burst errors, the parallel decoding technique has not been required so strongly. Therefore, there has not been a technique to decode a parallel received information, which has a large number of bits, in parallel by using a burst error detection and correction code such as the fire code. Thus, there is a problem that parallel decoding cannot be performed.